Publications and other reference materials referred to herein, including reference cited therein, are incorporated herein by reference in their entirety and are numerically referenced in the following text and respectively grouped in the appended Bibliography which immediately precedes the claims.
The concept of broadcast encryption was first introduced in [8] and further developed in many works including [14], [11], [2], [9], [7] and [12]. Broadcast encryption systems allow a broadcaster to send encrypted data to a set of users such that only a subset RS of authorized users can decrypt the data. A main challenge in constructing broadcast systems is ensuring that, even when the users that are not in RS collude, it is computationally infeasible for unauthorized users to decrypt a message.
Broadcast encryption systems support temporary revocation of users if revoked users are excluded from the set RS for a single ciphertext. Typically, in such systems, the identities of the revoked users are parameters in the encryption mechanism.
Broadcast encryption systems support permanent revocation of users if revoked users cannot decrypt any ciphertext after the revocation. Permanent user revocation is efficiently implemented in symmetric encryption schemes (e.g. the third scheme of [7]). Temporary revocation is achieved by various schemes including [5] and the first two schemes of [7].
Broadcast encryption systems are either stateful or stateless. A stateful scheme requires receivers to store a state and update it based on the ciphertexts they receive. Stateless receivers do not necessarily update a state. Stateless schemes are preferable in the sense that receivers do not have to be continuously online to update a state. However, stateful schemes open new avenues to achieve permanent revocation by basing decryption on the state and not enabling revoked users to correctly update a state. Furthermore, broadcast models in which the receivers can open a two-way channel to the broadcaster are becoming more prevalent, e.g. IPTV and Over-The-Top broadcasting. Given such two-way channels, receivers can update their state even if they go offline for a time.
A trivial solution for constructing collusion resistant broadcast system works as follows: The broadcaster maintains n independent encryption keys, while each user is granted his/her personal decryption key. The broadcaster encrypts each message with all of the encryption keys. Each user maintains a single private key, and decrypts a message by his/her private key. Since the keys are independent, collusion resistance is satisfied for any number of revoked colluding users. Obviously, this scheme is not efficient in the number of encryption/decryption keys, size of broadcaster storage, and cost of encryption/decryption procedure.
Protocols for stateful receivers have been introduced and analyzed in [10], [15], [3], [4], [18], and [16]. Most of the stateful symmetric encryption schemes are based on graph theory constructions, and support permanent revocation of a single user or a group of users. The protocols of [14] and [11] are based on the graph theoretic approach and provide permanent revocation of a single user or a group of users. The scheme of [11], based on the Layered Subset Difference technique, improves the results of [14], and shows that for any ε>0 one can create an efficient broadcast scheme (that supports users' revocation) with O(log1+ε n) keys, O(r) messages, and O(log n) cryptographic operations. Here r<n denotes a number of revoked users.
The best schemes of [16] require log n keys per update, linear server (broadcaster) storage of 2n−1 keys, and logarithmic user storage of log n keys. Nevertheless, all these schemes are based on the private (symmetric) keys encryption. The drawback of this approach is that only users that have the secret key, can receive and decrypt the broadcasted messages.
The stateless broadcast encryption schemes may be based on symmetric-key or public-key approach.
Stateless Symmetric Key Schemes
The most efficient stateless symmetric scheme of [7], based on Generalized Decisional Diffie-Hellman Exponent (GDDHE) assumption (Construction 3) provides users' revocation with the symmetric encryption and decryption keys of constant size and length of ciphertexts of the order O(r), where parameter r denotes the number of revoked users. The Construction 3 of [7] supports users permanent revocation.
The use of symmetric key cryptosystems restricts the solutions presented in [7] in the sense that only the server (or central module) may broadcast the sensitive data.
Stateless Public Key Schemes
The most used approach in creating collusion resistant broadcast or revocation systems is based on hardness of decisional algebraic problems in the groups of elliptic curves (for example Bilinear Decisional Diffie-Hellman (BDDH) problem). The broadcast encryption schemes for stateless receivers based on bilinear maps were proposed in [2] and further developed in [9]. The consequent constructions are compared regarding the efficiency parameters such as decryption/encryption keys and ciphertext sizes, and time complexity. Two constructions, based on bilinear maps, were introduced in [9]. In the first construction a ciphertext and private keys are of constant size, while public key length is linear in total number of receivers. The second construction achieves trade off between the ciphertext and public key length when both of them are of order O(√n) for any subset of receivers from a system of n users. The system uses constant size ciphertexts.
A powerful technique for public-key, broadcast encryption systems, is Attribute Based Encryption (ABE) (e.g., [5], [13]). The purpose of ABE is to establish access policy for decrypted data among users of a given set.
ABE was proposed in [17] as means for encrypted access control. The main idea of the ABE system is that ciphertexts are not necessarily encrypted for one particular user. Unlike traditional public-private key cryptography, user's private keys and ciphertexts are associated with a set of attributes that a user possesses. A user can decrypt a ciphertext if and only if he/she has a corresponding set of attributes associated with a security policy. In the Ciphertext Policy Attribute Based Encryption (CP-ABE) a user has to posses a certain set of attributes in order to access data.
The purpose of ABE is to establish access policy on who among the users of a given set can decrypt data. The number of keys used in ABE is logarithmic in the number of users, which provides the smallest possible number of keys ([6]). ABE ensures collusion resistance for any number of revoked colluding users. The main idea of the CP-ABE is that a user's private key is associated with (an arbitrary number of) attributes. A user is able to decrypt a ciphertext if there is a match between his/her attributes and the access structure of the ciphertext.
The paper [6] presents the proof of the basic schemes of [5]. In addition the basic ABE scheme is optimized in [6] by introducing the hierarchical structure of the attributes. Like other ABE based revocation systems, the scheme of [5] provides only temporary revocation of users.
Efficiency of the Broadcast Encryption Scheme
Efficiency is measured in server/user storage space, computational complexity of key update procedure and a number of messages sent upon join or revocation event.
Optimal efficiency is achieved for public key with temporary revocation by [12] and for symmetric key with permanent revocation by [7]. In both works,
the encryption/decryption keys are of constant size, ciphertext size is of O(r),
where r is the number of revoked users, and the computational complexity of a key update procedure is O(r).
Basic Ciphertext Policy ABE (CP-ABE) techniques were introduced and analyzed in [1]. Any user in [1] is assigned a set of attributes and can decrypt any ciphertext that embeds a policy, which satisfies the user's attributes. Furthermore, any coalition of users cannot decrypt a ciphertext if none of the user's attributes satisfies the policy.
A previous broadcast encryption work [5] bases broadcast encryption on CP-ABE. However, each revocation is temporary since sequentially revoked users (identified with different sets of attributes) can share their attribute keys and reconstruct the keys updated after their revocation.
The following table summarizes the classification of Broadcast Encryption methods used in the prior art publications referenced herein that discuss the subject of revocation.
PublicSymmetricRevocationstatefulstatelessStatefulstatelessTemporary[2], [5], [13], [9], [12]Permanent[10], [15], [3], [4], [18], [16], [14], 11][7]
From the above table it is seen that in the prior art there does not exist a public-key encryption method that supports permanent user revocation.
Therefore it is a purpose of the present invention to provide public-key encryption method that supports permanent user revocation.
It is another purpose of the present invention to extend known Ciphertext Policy ABE (CP-ABE) techniques to support permanent revocation.
It is another purpose of the present invention to provide a method for transforming public key broadcasting encryption methods with temporary revocation into methods with similar efficiency and permanent revocation.
Further purposes and advantages of this invention will appear as the description proceeds.